package linkedlist.leetcode_25_hard;

public class Recur {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode end = head;
        // 先走 k 步
        for (int i = 0; i < k; i++) {
            // 不足 k 个不进行反转
            if (end == null) {
                return head;
            }
            end = end.next;
        }
        // 对 head...end 这部分链表进行翻转，返回翻转后的头节点
        ListNode newHead = reverse(head, end);
        // 下一轮从 tail 开始
        // 翻转后 head 相当于尾节点，连接后面的链表（后面的链表递归继续翻转）
        head.next = reverseKGroup(end, k);
        return newHead;
    }

    public ListNode reverse(ListNode head, ListNode end) {
        ListNode pre = null;
        while (head != end) {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}
